package lc.q51_100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Q131 {

    public List<List<String>> partition(String s) {
        // 动态规划先预处理所有回文字符串
        boolean[][] dp = new boolean[s.length()][s.length()];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            // 数组左下角都是true，因为j比i大才需要比较
            for (int j = 0; j <= i; j++) {
                dp[i][j] = true;
            }
        }
        List<List<String>> result = new ArrayList<>();
        List<String> ans = new ArrayList<>();
        // 判断是否为回文。从后往前，这样的话就不会出现问题
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                // 如果s(i)与s(j)相等，那么判断(i + 1, j - 1)是否为回文就行
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1] [j - 1];
            }
        }
        // 处理是否
        dfs(s, 0, dp, result,ans);
        return result;
    }

    private void dfs(String s, int i, boolean[][] dp, List<List<String>> result, List<String> ans) {
        if (i == s.length()) {
            // 到最后了
            result.add(new ArrayList<>(ans));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            // 前面已经回文计算过了
            if (dp[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1, dp, result, ans);
                // 最后一个删掉
                ans.remove(ans.size() - 1);
            }
        }
    }


    public static void main(String[] args) {
        Q131 q131 = new Q131();
        System.out.println(q131.partition("aabb"));
    }

}
